from sys import stdin

def compute(n:int, arr:list[int])->None:
    # print(n,arr)
    arr.sort()
    ans = n
    an = arr[len(arr)-1]
    dp:list[bool] = [False]*(an+1)
    # print(dp)
    dp[0]=True
    for i in arr:
        if dp[i]:
            ans-=1
            continue
        for j in range(i,an+1):
            dp[j] = dp[j] or dp[j-i]
    # print(dp)
    print(f"{ans}")

input_strs = stdin.read().splitlines()
t:int = int(input_strs.pop(0).strip())

for _ in range(t):
    n:int = int(input_strs.pop(0).strip())
    arr:list[int] = list(map(int,input_strs.pop(0).strip().split(' ')))
    compute(n,arr)
